(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "No Title"

U'SO 'g5 16:5 J. NOEL 
Iml.OVement in the design mid 
: perigee of the ARPA network 
bit J. M. MQUILLAN, W. R. CROWTHER, B. P. CO, ELL, D.C. WALDEN, and.' 
F. E. 
rTI!OION 
Pt'ejects Agency 
m nwork 
 circuit, 
. whey 
er h 
at t 
The 
mtioa ta 
 of which 
.Ifil 1 .is mfdy modv,sd at the Ioiiowtnf node. 
The ARPA' N    n fro* over 
8yztems (c!!cd Hazts) and one communicatiorm pro- 
tenor called an Interlace Messe Procemor, or IMP. 
All of the Hcmtz st a site are. directly connected to the 
IMP. Some IMPs also provide the ability to connect 
terminals directly ta the network; thee are called 
Terminal Interface Mem,e rs, or TIPs. The 
I.IPa are connote[ together by a4deband telephone 
lin(. and provide a subnet through which the Hosts 
communicate. Each/ZiP may be onnected to as many 
as five other IMPs using telephone lines with band- 
widths from 9.6 to 230.4 kilobits per second. The typical 
bmdwidth is 50 kilobite. 
Dur/ng these. throe. years of network growth, the 
actual umr traffic has n light and network per- 
formnce under 8uch light toads haz been excellent. 
However, experimental traffic, as well M simulation 
studies, uncover,l logical fiwff in the IMP soltware 
which d.'a&4 performance at heavy loads The soft- 
ware was therdore eubstantially modified in the spring 
of 1972. This paper is !ar!y addmined to describing 
the new approaches which were taken. 
The first section of the pper coralder8 orne criteria 
of good network deziwn and then prezente our new 
algorithms in the areas of source. to-destination 
quenee and flow control, a well as our new I.MP-to.I.MP 
acknowledgment strategy. The second section addrese 
chages in program structure; the third Section ro- 
evalute the IMPes ' performance in light o! thee 
changez. The from section mention some broader 
The initial dign of the ARPA Network and the 
IMP wnz &,cribed at the 1970__nz JokLC,m.nn!er 
Con, and the TITdevelopment waz 
at the 1972 Sprimg Joint Corn_purer_Conference. t Theze 
papers ar. important background to a reading of the 
present pper. 
------------------------------<page break>-----------------------------
'JUL30 '95 16=26 J. NUbL UMiHrM 
742 
Fall Joint Computer Conlure,nee, 1972 
Fhu i--A!tPA netwurk, lugical map, Augtrot 1972 
NEW ALCiORITHMS 
A balanced dvign for a cummmxica[i.n system ]mukl 
proCde qck delivery of sho int,,rartiw, 
nd h bdwidth for lo tUes of datm. The IMP 
p w de  worm well under thine 
bim traffic ndio. The cxpeence of the first 
two d one half yc of the ARPA Network's opera- 
tion indioat that tim perred,ace goal of low dvlay 
hd  achieved. The lightly-loaded network d 
liver sho  ov mweral holm in 
untcnth of  cond. Moremyer, ewm umter heavy 
lo the delgy w airart Mwgys legs tlmn onehalf 
ond. The n%work al pmvi& go,d throughput 
rat for long m at light aml mxh'rate 
leve. However, the tmughput of the network 
 ificantly under hvy lo, so tlmt the 
of high bdwidth h not n oompletely liged. 
We lgt g problem in the initi network design 
which h  degrgtion under heavy 1oa. ' This 
problem inIv mes aiving at g destination 
IMP t a r fter th they cm he d,livo to the 
destingtion Hmt. We cl thh reusembly condition. 
Reembly congmon h to a comlition we fall 
reasbly letup in which the dtingtion 
incapable of ing ny traffic to its Hosts. Our al- 
rithm  event remcmbly cong,stimt aml 
relg sucnco control gorithm an &erib,.M 
the foRowg subsetion. 
Wc  found thgt the IMP and llne bandwidth 
rrements for hdling IMP-tM MP tr could 
suttiMly rueed. Improvements in tiffs area 
translate diret'tly into increases in thv maximum 
throughput ratv that an IMP can maintain. ()ur new 
alg,)rithm in this area is also $ven bclmv. 
Source-to-destinaffon flow control 
Fur efficiency, it is necessary to provide, .mewherv 
in the mtw,rk, a e.rtain amount of buffering 
thv urce attd dvtinatk, n Hosts, preferably an lOtltl t 
Vqual to the bandwidth of the channel between I 
Hots multiplivd by the round tp time over 
channel. The problem of flow control is to prvvent 
mvquges from entering the netwnrk for which network 
buffering b m)t available and which could congest the 
m,tw,rk and h,ad to remqembly lockup, t illustrattd 
in Figure 2. 
In Figure 2, IIP I is sending multi-packet 
to IMP 3; a lot. kup can occur when MI the rvtsembly 
buth,m ix lhlP 3 an' devoted to partially re:sembht 
:m',st's A and B. Since IMP :l h res,rw all its 
n'maining spm,v for :m'ait packets of the partially 
rc,:uql,ml)lmi nic.ae, it can only take in t}uxe l)artieu- 
lnr pa('kvts fr.m Ill' 2. T}le ,mt.tanding packeld. 
however, ar(. two ho away in IMP 1, They ratmc)t get 
through became IMP 2 is fi}l with to{md-forward 
packets of misag(,$ 0, D, and E (destined for IMP 3) 
which IMP 3 emmet yet accept. Thin, IMP 3 will never 
be able to eompletv the re;ombly of magt,a A 
and B. 
The original network deaix h,m ,uree-ttina- 
tion otlut,ll{'e aud flow control o,t the !itk mechanism 
previoqly report in Referene I and 5, Only a 8ingle 
mee ,m a given link w permitt il the subnet- 
w,rk at. one time, and uoneo numbera woro used to 
detect duPlieatv nues on a $ven hnk. 
We wew always awo that Htt$ e, mld defeat oxtr 
flow control leehanLm by %prayitxg" messages over 
inordillately large numar of links, but we counted on 
the nonmalieiu behavior of the Host to keep the 
IMP 1 
IMP 2 
f!{illml)l,f 
Fhturv 2--1teasembly lockup 
------------------------------<page break>-----------------------------
UL'30 '95 16:27 J. NOEL CHIAPHH 
hnprrvvm,,nts iu Dvslgn and P,.rf.rmam',..f ARPA Network 743 
number of lin in use below the. level at which problems 
occur. However, simulations ram Vxlwrlm'nts 
]oing the m,twork demonstrated that (..mmunivat 
lin cod defeat our flow control mthanim; further, 
it could be defeat by  number of Hosls communi- 
cating with a common te even though mwh Hmt 
only one link. Simulation ' show that re:omhly 
lkup may eventully eur wlwn owyr fiw links 
a ptieul Ht are simultmooly in ,. With ten 
or more links in e th mtlpket mesges, re- 
cmbly kmkup {e almt instmtly. 
If the buffeng is provid in the soarer IMP, ne 
tun optimize for low delay tmkio. It the buffer- 
lag is provid at the desttlon IMP, one el optimize 
for hi bandwidth trsmiom. Tb by eomsistent 
with o w of a beed eommunletions s)tem, 
we have devop  approh to reombly eon- 
gtion which ufili some buffer storage at both the 
urce mid dtination; our solution al> utilizes a 
request mhsm from source IMP to destination 
IMP.* 
$pificly, no multipckct me is allowed to 
enter the network unffi storage for the msago hm been 
1ocat at the destination IMP.  soon  the 
IMP tak in the fit packet of a multipket message, 
it nds a amPI control mc to the dtination IMP 
ruting that remmbly storage be rcser t the 
destlnatin for this nne. It dts not take in further 
kets from the Ht tii it relv  Mloration 
memae in reply. The dtintion IMP queues the 
rur md sen&s the ocation meo to tht. source 
IMP when enoch remmbly storage is fr'; ut this 
point the uree IMP n the m to the destina- 
tion. 
We mze the effective bdwidth for sequences 
of long mes by perilling 1 but the fit incasage 
to byp the rcut mhism. When the messuge 
it,ll $iv at the dfnution, md the dti;mtion 
IMP is ut o return the Ready-FoNext-Mesmtgt' 
(RFNM), the destination IMP waits until it. h rm 
for  &tioa mffitipket message. It then piggy- 
bcks  stor allstion on the RFNM. If the soee 
Ht is prompt in awing the RFNM with its next 
me, an Mlation is rely ztnd the tm'snge can lw 
trtt at once. If the e Ht delays t long, or 
if the dat transfer is compete, the mrce IMP returns 
tle un. titm to the destination. With this 
mechm we hve mini the intcr-m .e delay 
 Whl, mechanism is ,nilar to that implemenrM at xhe level of 
Host-lo-Hot protocol2 .?.u indic&tive of the